package ai.zixing.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandBotation {
    public static void main(String[] args) {
        // 先定义一个逆波兰表达式
        // 为了方便，数字和符号之间使用空格隔开
        String suffixExpression = "3 4 + 5 * 6 -";
        // 思路
        // 1. 先将表达式放入 ArrayList 中
        // 2.将 ArrayList 传递给一个方法，配合栈，完成计算
        List<String> rpnList = getListString(suffixExpression);
        System.out.println("rpnList = " + rpnList);
        int res = calculate(rpnList);
        System.out.println("计算的结果是 = " +  res);

    }

    // 将一个逆波兰表达式，依次将数据和运算符放入到一个 ArrayList 中
    public static List<String> getListString(String suffixExpression) {
        // 将 suffixExpression 分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    /**
     * 1）从左往右扫描，将 3和4入栈；
     * 2）遇到 + 运算符，弹出4和3，计算 4+3=7，再将7入栈；
     * 3）将5入栈；
     * 4）遇到 * 运算符，弹出 5和 7 计算 5*7=35，将35入栈；
     * 5）将6入栈；
     * 6）遇到 - 运算符，计算 35-6=29， 即计算结果
     * @param ls
     * @return
     */
    public static int calculate(List<String> ls) {
        Stack<String> stack = new Stack<>();
        for (String item : ls) {
            // 正则表达式
            if (item.matches("\\d+")) { // 匹配的是多位数
                // 入栈
                stack.push(item);
            } else {
                // pop 出两个数，并运算再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num1 + num2;
                } else if (item.equals("-")) {
                    res = num1 - num2;
                } else if (item.equals("*")) {
                    res = num1 * num2;
                } else if (item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                // res 入栈
                stack.push(res + "");
            }
        }
        return Integer.parseInt(stack.pop());
    }
}
